package listbyorder.access101_200.test126;

import java.util.ArrayList;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/9 13:30
 */
public class Solution1 {

    // DFS 回溯算法
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> ans = new ArrayList<>();
        List<String> path = new ArrayList<>();
        path.add(beginWord);
        dfs(beginWord, endWord, wordList, ans, path);
        return ans;
    }

    int min = Integer.MAX_VALUE;

    private void dfs(String beginWord, String endWord, List<String> wordList, List<List<String>> ans, List<String> path) {
        // 如果走到了最后的单词的位置
        if (beginWord.equals(endWord)) {
            if (path.size() < min) {
                // 如果当前长度小于min，集合清空
                ans.clear();
                min = path.size();
                ans.add(new ArrayList<>(path));
            } else if (min == path.size()) {
                ans.add(new ArrayList<>(path));
            }
            // 长度大于当前的min，不加入
            return;
        }

        // 如果当前的path的size大于min直接返回
        if (path.size() >= min) return;

        for (int i = 0; i < wordList.size(); i++) {
            String curWord = wordList.get(i);
            // 如果当前的字符已经添加过了，则跳过
            if (path.contains(curWord)) {
                continue;
            }
            // 判断两个单词是不是只相差一个字符
            if (oneDif(beginWord, curWord)) {
                path.add(curWord);
                dfs(curWord, endWord, wordList, ans, path);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean oneDif(String beginWord, String curWord) {
        int count = 0;
        for (int i = 0; i < beginWord.length(); i++) {
            if (beginWord.charAt(i) != curWord.charAt(i)) {
                count++;
            }
            if (count == 2) return false;
        }
        return count == 1;
    }
}
